package others;//import com.sun.xml.internal.bind.v2.util.StackRecorder;

import java.util.Arrays;

public class Test84 {
    /**
     * 84. 柱状图中最大的矩形
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * <p>
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     */

    public static int largestRectangleArea(int[] heights) {

        int count = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] == 0) {
                count++;
            }
        }
        int len = heights.length;
        int res = 0;
        if (count == 0) {
            res = largestRectangleArea1(heights);
        } else {
            for (int i = 0; i < len; i++) {
                if (heights[i] == 0) {
                    int[] ints = copyOf(heights, i + 1, 0);
                    int[] ints1 = copyOf(heights, heights.length - i, i + 1);
                    int i1 = largestRectangleArea1(ints);
                    int i2 = largestRectangleArea1(ints1);
                    res = Math.max(i1, i2);

                    System.out.println(Arrays.toString(ints));
                    System.out.println(Arrays.toString(ints1));
                }
            }
        }

        return res;
    }

    public static int largestRectangleArea1(int[] heights) {
        Arrays.sort(heights);
        int len = heights.length;
        int res = 0;
        for (int i = len; i > 0; i--) {
            for (int j = 0; j <= len - i; j++) {
                res = (i) * heights[j] > res ? (i) * heights[j] : res;
            }
        }
        return res;
    }

    //拷贝数组元素
    public static int[] copyOf(int[] arr, int newLength, int index) {
        int[] newarr = new int[newLength]; // 定义一个数组给
        for (int i = index; i < newLength; i++) { //循环从数组下标0拷贝到newLength这个下标为值
            newarr[i] = arr[i]; //把原始数组中取出来放入新数组中进去
        }
        return newarr; //返回一个数组
    }

    public static void main(String[] args) {
        int arr[] = {2,1,2};
        System.out.println(largestRectangleArea(arr));
    }
}
